Hardware-oriented stream ciphers are designed to be run on dedicated hardware. They typically work on the bit-level, since hardware can be custom-tailored to be more efficient with these operations. Almost all hardware stream ciphers are built upon a concept called feedback shift registers (FSRs).
An FSR is comprised of a bit array, called a register, which is equipped with an update feedback function, denoted as
The current state |
denotes the OR operation.
For example, suppose you had a feedback function,
Given a feedback function
With the above function,
Naturally, an FSR with a larger period will produce a more unpredictable output.
Linear Feedback Shift Registers are FSRs which are equipped with a linear feedback function, namely a procedure which XORs together some of the bits of the current state. The bits that get XOR-ed together are defined by a set of boolean feedback coefficients. It is important that the feedback coefficients are not allowed to mutate throughout any update, since they define the feedback function. The number of bits in the bit array of the register is called its degree.
For a register consisting of bits
For each clock tick, the LFSR outputs the value of the right-most bit,
The maximal period of an LFSR is
LFSRs are inherently insecure due to their linearity. Given known feedback coefficients, the first
It is possible to show that for a maximal period LFSR the equations in the system are linearly independent (
LFSRs can be strengthen by introducing nonlinearity in the encryption process by different means. This means that it is not only XOR operations that are used, but also logical ANDs and ORs. For example, it is possible to make the feedback loop nonlinear by setting the value of the leftmost bit at each clock tick to be a nonlinear function of the bits in the previous state. If the register's state at time
As before, the rightmost bit,
Unfortunately, there is a downside to NFSRs (Nonlinear FSRs). There is no efficient way to determine an NFSR's period or even whether its period is maximal. It is however, possible to mitigate this by combining NFSRs and LFSRs, which is what Grain-128a does.
In the above example, the FSR itself is nonlinear, since the way that the leftmost is altered at each clock tick is determined by a nonlinear function. However, it is also possible to keep the FSR linear and instead pass its output to a filter function,
Whilst filtered FSRs are stronger than LFSRs, their underlying partial linearity makes them vulnerable to complex attacks such as algebraic attacks, cube attacks, and fast correlation attacks.